package 数组;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/two-sum/
 */
public class _1_两数之和 {
    //仅仅针对有序数组
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums); //先排序
        int lo = 0;
        int hi = nums.length - 1;
        while(lo<hi){
            int sum = nums[lo] + nums[hi];
            if(sum == target){
                return new int[]{lo,hi};
            }else if(sum < target){
                lo++;
            }else {
                hi--;
            }
        }
        return new int[]{-1,-1};
    }

    //使用哈希表做
    public int[] twoSum2(int[] nums, int target) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(nums[i],i); //数组值为key,索引为value
        }

        for (int i = 0; i < n; i++) {
            int other = target - nums[i];
            if(map.containsKey(other) && map.get(other)!= i){
                return new int[]{i,map.get(other)};
            }
        }
        return new int[]{};
    }
}
